#include <vector>
#include <string>
#include <queue>
#include <unordered_map>

using namespace std;

// 1971. 寻找图中是否存在路径
class Solution1
{
public:
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) 
    {
        vector<int> ufs(n, -1);
        auto findRoot = [&ufs](int x)
        {
            int root = x;
            // 找根
            while(ufs[root] >= 0)
            {
                root = ufs[root];
            }

            // 路径压缩
            while(ufs[x] >= 0)
            {
                int parent = ufs[x];
                ufs[x] = root;
                x = parent;
            }

            return root;
        };

        for(auto& edge : edges)
        {
            int root1 = findRoot(edge[0]);
            int root2 = findRoot(edge[1]);
            // 合并两个集合
            if(root1 != root2)
            {
                // 顺序不能颠倒
                ufs[root1] += ufs[root2];
                ufs[root2] = root1;
            }
        }

        return findRoot(source) == findRoot(destination);
    }
};

// 684. 冗余连接
class Solution2
{
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) 
    {
        int n = edges.size();
        vector<int> ufs(n + 1, -1);
        auto findRoot = [&ufs](int x)
        {
            int root = x;
            while(ufs[root] >= 0)
            {
                root = ufs[root];
            }

            while(ufs[x] >= 0)
            {
                int parent = ufs[x];
                ufs[x] = root;
                x = parent;
            }

            return root;
        };

        for(auto& edge : edges)
        {
            int root1 = findRoot(edge[0]);
            int root2 = findRoot(edge[1]);
            if(root1 != root2)
            {
                ufs[root1] += ufs[root2];
                ufs[root2] = root1;
            }
            else 
                return edge;
        }

        return vector<int>();
    }
};

// 685. 冗余连接 II
class Solution3
{
private:
    static const int N = 1010;
    int ufs[N];
    int n; // 边的数量

    // 初始化并查集
    void init()
    {
        for(int i = 1; i <= n; ++i)
        {
            ufs[i] = -1;
        }
    }

    // 找出根
    int find(int x)
    {
        int root = x;
        while(ufs[root] >= 0)
        {
            root = ufs[root];
        }

        while(ufs[x] >= 0)
        {
            int parent = ufs[x];
            ufs[x] = root;
            x = parent;
        }

        return root;
    }

    // 将 v 添加到 u 所在的集合中
    void join(int u, int v)
    {
        int root1 = find(u);
        int root2 = find(v);

        if(root1 != root2)
        {
            ufs[root1] += ufs[root2];
            ufs[root2] = root1;
        }
    }

    // 判断 u 和 v 是否在同一个集合
    bool same(int u, int v)
    {
        return find(u) == find(v);
    }

    // 删除指定的边后，判断是不是树
    bool isTreeAfterRemoveEdge(vector<vector<int>>& edges, int deleteEdge)
    {
        init();
        for(int i = 0; i < n; ++i)
        {
            if(i == deleteEdge) continue;
            if(same(edges[i][0], edges[i][1])) return false; // 构成有向环，一定不是树
            join(edges[i][0], edges[i][1]);
        }
        return true;
    }

    // 在有向图里找到删除的那条边，使其变成树
    vector<int> getRemoveEdge(vector<vector<int>>& edges)
    {
        init();
        for(int i = 0; i < n; ++i)
        {
            if(same(edges[i][0], edges[i][1])) return edges[i]; // 构成有向环，这条边就是要删除的边
            join(edges[i][0], edges[i][1]);
        }
        return {};
    }

public:
    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) 
    {
        int inDegree[N] = {0}; // 记录节点入度
        n = edges.size(); // 边的数量
        for(int i = 0; i < n; ++i)
        {
            ++inDegree[edges[i][1]]; // 统计入度
        }

        vector<int> v; // 记录入度为 2 的边（如果有的话就两条边）
        // 找出最后出现在二维数组中的答案
        for(int i = n - 1; i >= 0; --i)
        {
            if(inDegree[edges[i][1]] == 2) v.push_back(i);
        }

        // 如果有入度为 2 的节点，那么一定是两条边里删掉一条，看删哪一条构成树
        if(v.size() > 0)
        {
            if(isTreeAfterRemoveEdge(edges, v[0]))
                return edges[v[0]];
            else
                return edges[v[1]];
        }

        // 明确没有入度为 2 的情况，那么一定是有有向环，找到构成环的边返回即可
        return getRemoveEdge(edges);
    }
};

// 1319. 连通网络的操作次数
class Solution4
{
public:
    int makeConnected(int n, vector<vector<int>>& connections) 
    {
        if(connections.size() < n - 1) return -1;

        vector<int> ufs(n, -1);
        auto findRoot = [&ufs](int x)
        {
            int root = x;
            while(ufs[root] >= 0)
            {
                root = ufs[root];
            }
            while(ufs[x] >= 0)
            {
                int parent = ufs[x];
                ufs[x] = root;
                x = parent;
            }
            return root;
        };

        int ret = n; // 需要连接的节点数
        for(int i = 0; i < connections.size(); ++i)
        {
            int root1 = findRoot(connections[i][0]);
            int root2 = findRoot(connections[i][1]);
            if(root1 != root2)
            {
                ufs[root1] += ufs[root2];
                ufs[root2] = root1;
                --ret;
            }
        }

        // 剩余 ret 的节点未连接，至少需要 ret - 1 条边
        return ret - 1;
    }
};

// 1202. 交换字符串中的元素
class Solution 
{
public:
    string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) 
    {
        int n = s.size();
        vector<int> ufs(n, -1);
        auto findRoot = [&](int x)
        {
            int root = x;
            while(ufs[root] >= 0)
            {
                root = ufs[root];
            }

            while(ufs[x] >= 0)
            {
                int parent = ufs[x];
                ufs[x] = root;
                x = parent;
            }
            return root;
        };

        for(int i = 0; i < pairs.size(); ++i)
        {
            int root1 = findRoot(pairs[i][0]);
            int root2 = findRoot(pairs[i][1]);
            if(root1 != root2)
            {
                ufs[root1] += ufs[root2];
                ufs[root2] = root1;
            }
        }

        string ret(s);
        unordered_map<int, priority_queue<char, vector<char>, greater<char>>> m;
        for(int i = 0; i < n; ++i)
        {
            m[findRoot(i)].push(s[i]);
        }

        for(int i = 0; i < n; ++i)
        {
            ret[i] = m[findRoot(i)].top();
            m[findRoot(i)].pop();
        }
        return ret;
    }   
};